#include <iostream>

using namespace std;

// 382. 链表随机结点
// 给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
// https://leetcode.cn/problems/linked-list-random-node/description/

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
private:
    ListNode* head;
public:
    Solution(ListNode* head) {
        this->head = head;
    }
    // 返回一个随机的node的值
    int getRandom() {
        int res = head->val;
        ListNode* cur = head->next; // 首节点的下一个
        int index = 1;

        while (cur != NULL) {
            int rnd = rand() % (index + 1); // [0, index]
            if(rnd == 0)
                res = cur->val;

            cur = cur->next;
            index++;
        }

        return res;

    }
};

int main() {
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution* obj = new Solution(head);
     * int param_1 = obj->getRandom();
    */
    Solution* obj = new Solution([1,2,3])
    return 0;
}
